//
// Created by wangxiaodong on 2017/11/25.
//

#ifndef SELECTIONSORT_INSERTIONSORT_H
#define SELECTIONSORT_INSERTIONSORT_H

#include <ostream>
using namespace std;

/**
 * 插入排序 如果在相对有序或者数据量大单范围小的情况下， 由于插入排序可以提前结束第二层循环，因此速度远比选择排序快。
 */
namespace InsertionSort{

    /**
     * 存在频繁空间交换问题
     * @tparam T
     * @param arr
     * @param len
     */
    template <typename T>
    void insertionSort(T arr[], int len){
        for (int i = 1; i < len; ++i) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; --j)
                swap(arr[j],arr[j - 1]);

        }
    }

    /**
     * 优化插入排序，减少频繁空间交换问题
     * @tparam T
     * @param arr
     * @param len
     */
    template <typename T>
    void insertionSortOpt(T arr[], int len){
        for (int i = 1; i < len; ++i) {
            T val = arr[i]; //缓存要被排序的数
            int j = i; // 缓存要被排序的数的位置
            for (; j > 0 && arr[j - 1] > val; --j) {
                // 如果前面的大于被排序数，将前面的移动到后面，并记录被排序数的新位置
                arr[j] = arr[j - 1];
            }
            // 找到被排序数的新位置
            arr[j] = val;
        }
    }




}
#endif //SELECTIONSORT_INSERTIONSORT_H
